﻿//907. 子数组的最小值之和
//给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
//由于答案可能很大，因此 返回答案模 10 ^ 9 + 7 。


class Solution {
public:
    const int MOD = 1e9 + 7;
    int sumSubarrayMins(vector<int>& arr)
    {
        long long ans = 0;
        // left 小于或等于 arr[i]的数下标  right 小于 arr[i]   
        arr.push_back(-1);
        int n = arr.size();
        stack<int> sta;
        sta.push(-1);
        for (int i = 0; i < n; i++)
        {
            //单调递增
            while (sta.size() > 1 && arr[sta.top()] > arr[i])
            {
                // left = sta.top
                int cur = sta.top();
                sta.pop();
                ans += (long long)arr[cur] * (cur - sta.top()) * (i - cur);
            }
            sta.push(i);
        }
        return ans % MOD;
    }
};